package com.hr.leetcode.分治和递归和回溯;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author 周恒哲
 * @date 2020/05/21
 **/
public class _438_找到字符串中所有字母异位词 {
    public static List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        // 记录最短子串的开始位置和长度
        int start = 0, minLen = Integer.MAX_VALUE;
        int left = 0, right = 0;

        // 相当于两个计数器
        Map<Character, Integer> window = new HashMap<Character, Integer>();
        Map<Character, Integer> needs = new HashMap<Character, Integer>();

        for (int i = 0; i < p.length(); i++) {
            /**
             * 相当于：
             * int count = needs.getOrDefault(p.charAt(i), 0);
             * needs.put(p.charAt(i), count + 1);
             */
            needs.put(p.charAt(i), needs.getOrDefault(p.charAt(i), 0) + 1);//将p中字符串出现的值放入其中
        }

        // 记录 window 中已经有多少字符符合要求了
        int match = 0;

        while (right < s.length()) {
            char c1 = s.charAt(right);//获取当前right处于什么位置
            if (needs.containsKey(c1)) {//如果needs包含right当前的值
                window.put(c1, window.getOrDefault(c1, 0) + 1);//当Map集合中有这个key时，就使用这个key值，如果没有就使用默认值defaultValue
                if (window.get(c1).compareTo(needs.get(c1)) == 0)
                    // 字符 c1 的出现次数符合要求了
                    match++;
            }
            //right继续前进找可行解
            right++;

            // window 中的字符串已符合 needs 的要求了
            while (match == needs.size()) {//3
                if (right - left == p.length()) {
                    res.add(left);
                }
                //开始进行优化，即缩小区间，删除s[left]
                char c2 = s.charAt(left);
                if (needs.containsKey(c2)) {
                    window.put(c2, window.get(c2) - 1);

                    if (window.get(c2) < needs.get(c2))
                        // 字符 c2 出现次数不再符合要求
                        match--;
                }
                left++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        _438_找到字符串中所有字母异位词.findAnagrams("cbaebabacd","abc");
    }
}
